package practice2;

import java.util.Arrays;

/**
 * # 问题描述
 * <p>
 * 环状 DNA 又称超螺旋，即一段碱基序列呈现环状，
 * 在分析时，需要将相同序列的环状 DNA 分到相同组内，现需将环状碱基序列按照最小表示法进行排序。
 * <p>
 * 一段长度为 `n` 的碱基序列，按照顺时针方向，碱基序列可以从任意位置起开始该序列顺序，
 * 因此长度为 `n` 的碱基序列有 `n` 种表示法。
 * 例如：长度为 6 的碱基序列 `CGAGTC`，有 `CGAGTC`、`GAGTCC`、`AGTCCG` 等表示法。
 * 在这些表示法中，字典序最小的称为“最小表示”。
 * <p>
 * 输入一个长度为 `n`（`n <= 100`）的环状碱基序列（只包含 `A`、`C`、`G`、`T` 这 4 种碱基）
 * 的一种表示法，输出该环状碱基序列的最小表示。
 * <p>
 * 例如：
 * `ATCA` 的最小表示是 `AATC`
 * `CGAGTC` 的最小表示是 `AGTCCG`
 * <p>
 * ## 输入描述
 * <p>
 * 一段 DNA 碱基序列
 * <p>
 * ## 输出描述
 * <p>
 * DNA 碱基序列的最小表示
 * <p>
 * **备注**：
 * `n <= 100`
 * DNA 由大写英文字母 `A`、`G`、`C`、`T` 组成
 * <p>
 * **示例 1**
 * 输入：`ATCA`
 * 输出：`AATC`
 * <p>
 * **示例 2**
 * 输入：`CGAGTC`
 * 输出：`AGTCCG`
 */
public class Main {
    public static String solution(String dna_sequence) {
        // Please write your code here
        int len = dna_sequence.length();
        if (len >= 1) {
            String[] arr = new String[len];     // 所有的序列表示法
            StringBuilder sb = new StringBuilder();     // StringBuilder拼接字符串更高效；在循环外创建，减少对象的创建和销毁
            for (int i = 0; i < len; i++) {
                String front = dna_sequence.substring(i);
                String back = dna_sequence.substring(0, i);
                sb.append(front).append(back);
                arr[i] = sb.toString();
                sb.setLength(0);        // 清空sb
            }
            Arrays.sort(arr);       //默认升序排序
            //System.out.println(arr[0]);
            return arr[0];
        }
        //碱基序列无效
        System.out.println("Invalid DNA sequence!");
        return "";
    }

    public static void main(String[] args) {
        // You can add more test cases here
        System.out.println(solution("ATCA").equals("AATC"));
        System.out.println(solution("CGAGTC").equals("AGTCCG"));
        System.out.println(solution("TCATGGAGTGCTCCTGGAGGCTGAGTCCATCTCCAGTAG").equals("AGGCTGAGTCCATCTCCAGTAGTCATGGAGTGCTCCTGG"));
    }
}